package me.mingshan.leetcode;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author hanjuntao
 * @date 2025/10/12 0012
 */
public class L_1372_二叉树中最长交错路径 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.left.right = new TreeNode(6);
        root.right.right.left.right.right = new TreeNode(7);
        System.out.println(longestZigZag(root)); // 3

        System.out.println(getCurrMax("0101"));
    }

    /**
     * 思路：
     * 1. 递归遍历二叉树，记录路径方向，并计算路径长度
     * 2. 获取当前路径长度，并更新最大长度
     * 3. 递归处理左子树和右子树
     *
     * 这样在叶子节点，最后再计算长度，会超时。
     *
     * 可以在遍历路径时，动态的计算路径长度
     *
     * @param root
     * @return
     */
    public static int longestZigZag(TreeNode root) {
        AtomicInteger max = new AtomicInteger(0);
        // 记录路径的方向，0表示左，1表示右
        dfs(root, null, "", max);

        return max.get();
    }

    private static void dfs(TreeNode root, TreeNode parent, String path, AtomicInteger max) {
        if (root == null) {
            return;
        }

        // 判断当前节点和父节点的连接方向
        if (parent != null) {
            int direction = parent.left == root ? 0 : 1;
            path += direction;
        }
        // 如果当前为叶子节点，则计算路径长度
        if (root.left == null && root.right == null) {
            System.out.println("path:" + path);

            // 计算路径长度(相邻的都不一样)
            if (path.length() > 1) {
                int currMax = getCurrMax(path);
                max.set(Math.max(max.get(), currMax));
            }
        }

        dfs(root.left, root, path, max);
        dfs(root.right, root, path, max);
    }

    private static int getCurrMax(String path) {
        int currMax = 1;
        int count = 1;
        for (int i = 1; i < path.length(); i++) {
            String curr = String.valueOf(path.charAt(i));
            String prev = String.valueOf(path.charAt(i - 1));
            if (!curr.equals( prev)) {
                count++;

                currMax = Math.max(currMax, count);
            } else {
                count = 1;
            }
        }
        return currMax;
    }
}
